1. Field of the Invention
The present invention relates to a system and method for decreasing the route convergence time in a wireless communication network, such as a wireless ad-hoc peer-to-peer network, by finding an alternate route if the nodes anticipate weakening or breakage of a route currently in use. More particularly, the present invention relates to a system and method which enables reactive routing protocols to find optimal routes between nodes in these types of networks when those routes cannot otherwise be found in certain conditions.
2. Description of the Related Art
Wireless communication networks, such as mobile wireless telephone networks, have become increasingly prevalent over the past decade. These wireless communications networks are commonly referred to as “cellular networks”, because the network infrastructure is arranged to divide the service area into a plurality of regions called “cells”. A terrestrial cellular network includes a plurality of interconnected base stations, or base nodes, that are distributed geographically at designated locations throughout the service area. Each base node includes one or more transceivers that are capable of transmitting and receiving electromagnetic signals, such as radio frequency (RF) communications signals, to and from mobile user nodes, such as wireless telephones, located within the coverage area. The communications signals include, for example, voice data that has been modulated according to a desired modulation technique and transmitted as data packets. As can be appreciated by one skilled in the art, network nodes transmit and receive data packet communications in a multiplexed format, such as time-division multiple access (TDMA) format, code-division multiple access (CDMA) format, or frequency-division multiple access (FDMA) format, which enables a single transceiver at a first node to communicate simultaneously with several other nodes in its coverage area.
In recent years, a type of mobile communications network known as an “ad-hoc” network has been developed. In this type of network, each mobile node is capable of operating as a base station or router for the other mobile nodes, thus eliminating the need for a fixed infrastructure of base stations. More sophisticated ad-hoc networks are also being developed which, in addition to enabling mobile nodes to communicate with each other as in a conventional ad-hoc network, further enable the mobile nodes to access a fixed network and thus communicate with other mobile nodes, such as those on the public switched telephone network (PSTN), and on other networks such as the Internet. Details of these advanced types of ad-hoc networks are described in U.S. Pat. No. 7,072,650 entitled “Ad Hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks”, granted on Jul. 4, 2006 ,in U.S. Pat. No. 6,807,165 entitled “Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel”, granted on Oct. 19, 2004, and in U.S. Pat. No. 6,873,839 entitled “Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System”, granted on Mar. 29, 2005, the entire content of each being incorporated herein by reference.
Two of the routing protocols being considered by IETF for mobile ad-hoc networks (MANET) are Ad-Hoc On-Demand Distance Vector (AODV) Routing Protocol as described, for example, in a publication by Charles E. Perkins, Elizabeth M. Belding-Royer, and Samir Das entitled “Ad Hoc On Demand Distance Vector (AODV) Routing.” IETF Experimental RFC, July 2003, and Dynamic Source Routing (DSR) protocol as described in a publication by David B. Johnson, David A. Maltz and Yih-Chun Hu entitled “The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks (DSR)” IETF Internet draft, July 2004 , the entire content of both documents being incorporated herein by reference.
As can be appreciated by one skilled in the art, On-Demand routing protocols create routes only when desired by the source node, that is, the node that is attempting to transmit a data packet. When a node requires a route to a destination, it initiates a route discovery process within the network. This process is completed once a route is found or all possible route permutations have been examined. Once a route has been established, the route is maintained by some form of route maintenance procedure until either the destination becomes inaccessible along every path from the source or until the route is no longer desired.
As described in the publication by Perkins et al. cited above, a node following these On-Demand routing protocols initiates processing for a special message called as Route Error (RERR) in the following situations: if the node detects a link break for the next hop of an active route in its routing table while transmitting data (and route repair, if attempted, was unsuccessful), of if the node gets a data packet destined to a node for which it does not have an active route and is not repairing (if using local repair), or if the node receives a RERR from a neighbor for one or more active routes. In summary, the Route Error message is sent only when a node is absolutely sure that the link towards the next hop is unavailable.
As further described in the Perkins et al. publication, to detect link connectivity (or breakage), a node can use one of the following techniques. Any suitable link layer notification, such as those provided by IEEE 802.11, can be used to determine connectivity, each time a packet is transmitted to an active next hop. For example, absence of a link layer ACK or failure to get a CTS after sending RTS, even after the maximum number of retransmission attempts, indicates loss of the link to this active next hop. If layer-2 notification is not available, passive acknowledgment should be used when the next hop is expected to forward the packet, by listening to the channel for a transmission attempt made by the next hop. If transmission is not detected within NEXT_HOP_WAIT milliseconds or the next hop is the destination (and thus is not supposed to forward the packet), one of the following methods should be used to determine connectivity: receiving any packet (including a Hello message) from the next hop; a route request (RREQ) unicast to the next hop, asking for a route to the next hop; or an Internet Control Message Protocol (ICMP) Echo Request message unicast to the next hop.
Although these techniques are somewhat suitable, certain problems exist which impede their ability to detect link connectivity. For example, these techniques can erroneously indicate breakage of link because of a fail in packet transmission while a packet transmission can fail due to congestion rather than movement of node or breakage of link. Sending a route error message will delete the route maintained by several nodes to the node in question, thus forcing the nodes interested in sending packets to the node in question to restart the bandwidth-expensive route discovery process. Secondly, link layer will only inform the upper layers of failure after it has failed to transmit the packet after several retrials, which may be separated by considerable time and hence, significant delay will be accrued before triggering upper layers to respond.
Certain problems also exist with the passive acknowledgement techniques discussed above. That is, although passive acknowledgement has a very low probability of producing a false alarm, it has very long delay associated with the alarm process. For example, the number of hellos that need to be missed before a link break is declared needs to be of the order of n or more because of the low broadcast reliability of the wireless channel, where n can be as high as 5 or 10, or possibly more. Also, in both the link layer notification and passive acknowledgment techniques, any attempt to repair the route or find another route will be initiated only after the node attempting to send the data packet has determined that a break in the link exists. Hence, there is no “make before break” mechanism that is performed for either of these techniques.
Another problem with the On-Demand protocols discussed above is the optimization technique that they typically use to reduce the overhead in finding routes. This optimization technique is typically known as an “expanding ring search” in which the number of hops that a broadcast RREQ can travel is controlled as described the Perkins et al. publication cited above. Specifically, to prevent unnecessary network-wide dissemination of RREQs, the originating node should use an expanding ring search technique. In an expanding ring search, the originating node initially uses a Time to Live (TTL) value of TTL=TTL_START in the RREQ packet IP header and sets the timeout for receiving a route reply (RREP) to RING_TRAVERSAL_TIME milliseconds. The TTL_VALUE used in calculating RING_TRAVERSAL_TIME is set equal to the value of the TTL field in the IP header. If the RREQ times out without a corresponding RREP, the originator broadcasts the RREQ again with the TTL incremented by TTL_INCREMENT. This continues until the TTL set in the RREQ reaches TTL_THRESHOLD, beyond which a TTL=NET_DIAMETER is used for each attempt. Each time, the timeout for receiving a RREP is RING_TRAVERSAL_TIME. When it is desired to have all retries traverse the entire ad-hoc network, this can be achieved by configuring TTL_START and TTL_INCREMENT both to be the same value as NET_DIAMETER. Accordingly, this optimization (expanding ring search technique) may result in the problem illustrated by the following example network shown in FIG. 1.
Specifically, as shown in FIG. 1, a circle represents a node and lines (dashed or straight) represent the wireless link between the nodes. As indicated, all the links (if they exist) are good except the one between the nodes B and E. It is also assumed that the nodes do not have routes with each other. In this example, if node A wants to communicate with node E and uses the expanding ring search as described above, it will start with TTL=1. Hence, initially the RREQ will be received by nodes B and C. Assuming that these nodes do not know a route to node E, they will simply drop the RREQ after performing the processing as required as per the protocol. Since the TTL used is 1 initially, the RREQ packet will not be forwarded. After the timeout period, node A will resend RREQ with increased TTL which in this case will be 2 (new TTL=2 times old TTL). This time again the RREQ will be first received by nodes B and C. Since this time the value of TTL is 2, the RREQ will be forwarded by them. The RREQ forwarded by node C is received at nodes A and D. Node A ignores the message as it is the source of RREQ and node D drops it after updating the routing table as specified by protocol. Node D drops the RREQ because it can neither reply to it (as it doesn't have a route to E) nor can it forward it (as the TTL was set to 2 and has already traveled two hops). The RREQ forwarded by node B is received by nodes A and E. Node A ignores the message as it is the source of RREQ.
It should be noted that although the link between the nodes B and E is “bad”, a small packet can still be sent due to the characteristic of a wireless channel and repeated retrial by the MAC layer. When node E receives the RREQ, it immediately replies with a RREP since it is the destination identified in the RREQ packet. This time, node A should receive the RREP before the expiration of its timer and hence it will not generate any new RREQ with a higher TTL value. Thus, node A chooses route via B to E, and the route through nodes C and D is not computed. In this particular case, the route through nodes C and D may be optimal because of better links. However, the link between nodes B and E can be so bad that it does not allow larger data packets to go through and hence may not even be a useful route. If this is the case and node B is not able to send data packets successfully, it will generate a route error for node E to A. Node A will therefore restart the Route Discovery process and may get the same route because of the reasons explained above. Hence, the optimal route is never found and network bandwidth is wasted by repeated route discoveries.
Another problem with the On-Demand routing protocols is their instantaneous nature of finding routes. On-Demand routing protocols find routes as needed and do not attempt to find any alternate route unless the current route is broken. The route found initially may be the optimal route (based on the metrics used) at that particular instant of time, but as time progresses, it may not be the best route due to node mobility, congestion and so on. Hence, this behavior can lead to inefficient routes and under utilization of network resources.
Accordingly, a need exists for a system and method that is capable of finding optimal routes in a wireless communication network without the drawbacks associated with the existing techniques as described above.